/*
 * @lc app=leetcode.cn id=201 lang=cpp
 *
 * [201] 数字范围按位与
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    long long commonPrefix(long long left, long long right)
    {
        long long prefix = (long long)1 << 31;
        while (right < prefix)
        {
            prefix >>= 1;
        }
        //此时有 left <= prefix <= right 或者 prefix < left
        if (prefix < left)
        {
            return prefix |= rangeBitwiseAnd(left & (prefix-1), right & (prefix - 1));
        }
        // if(prefix >= left && prefix <= right)
        // 此时有 left <= prefix <= right
        if (prefix - 1 >= left)
            return 0;
        else
            return prefix;
    }
    int rangeBitwiseAnd(long long left, long long right)
    {
        if (left == 0 || right == 0)
            return 0;
        if (left == right)
            return left;
        
        return commonPrefix(left, right);
    }
};
// int main()
// {
//     cout << Solution().rangeBitwiseAnd(5, 7) << endl;
//     return 0;
// }
// @lc code=end
